
<template>
<div>
    <h1>掌握递归的实现原理，能做3个递归的常见题</h1>
</div>
</template>

<script>
//1. 阶乘（Factorial）：
// 阶乘是指将一个正整数 n 与小于等于它的正整数相乘的结果，通常用符号 "!" 表示。阶乘的递归定义如下：
// n! = n * (n-1)!
// 1! = 1
// 递归实现示例代码：
function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 输出: 120

// 斐波那契数列（Fibonacci Sequence）：
// 斐波那契数列是指每个数字都是前两个数字之和的数列。斐波那契数列的递归定义如下：
// F(0) = 0
// F(1) = 1
// F(n) = F(n-1) + F(n-2) (n >= 2)
function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 输出: 8

// 3.二叉树遍历：
// 二叉树是由节点组成的树结构，每个节点最多有两个子节点，左子节点和右子节点。常见的二叉树遍历方式有前序遍历（Pre-order traversal）、中序遍历（In-order traversal）和后序遍历（Post-order traversal）。这里以前序遍历为例进行递归实现。

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function preOrderTraversal(node) {
  if (node === null) {
    return;
  }
  console.log(node.value);
  preOrderTraversal(node.left);
  preOrderTraversal(node.right);
}

// 创建二叉树
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

// 前序遍历
preOrderTraversal(root);
// 输出: 1 2 4 5 3
// 以上是三个常见递归问题的 JavaScript 实现示例。递归的实现原理是利用函数自身调用来解决问题，通过不断地将问题分解为更小的子问题，直到达到基本情况（递归终止条件），然后再依次将子问题的解合并起来得到最终的解。

</script>
<style scoped lang='scss'>

</style>
